//第一种方法第一层dfs递归起点，第二层dfs从起点开始判断是否存在路径和为target
class Solution {
public:
    int _pathSum(TreeNode* root,long targetSum)
    {
        if(root == nullptr)
        {
            return 0;
        }
        int ret = 0;
        if(root->val == targetSum)
        {
            ret++;
        }
        ret+=_pathSum(root->left,targetSum-root->val);
        ret+=_pathSum(root->right,targetSum-root->val);
        return ret;
    }//这个函数的目的就是计算这个路径和上是否存在和为targetsum的值，最后使用ret进行返回
    int pathSum(TreeNode* root, int targetSum) {
       //第一种方法使用dfs去进行寻找，首先以root为开始位置往后去进行递归寻找是否存在路径和为targetsum
       //但是这只是以root为开始位置的路径和，还要去递归其它的节点以其它的节点为开始，寻找路径和为targetsum
       int ret = 0;
       if(root == nullptr)
       {
            return 0;
       } 
       ret+= _pathSum(root,targetSum);
       ret+=pathSum(root->left,targetSum);
       ret+=pathSum(root->right,targetSum);//递归以其它的节点为开始位置往后递归
       return ret;
    }
};
//第二种方法：
class Solution {
public:
    int ret = 0;

    void _pathSum(TreeNode* node, unordered_map<long, long>& cnt, long path, int targetSum) {
        if (node == nullptr) {
            return;
        }
        
        path += node->val; // 更新当前路径和
        
        // 检查是否存在从某个上层节点到当前节点的路径和为 targetSum
        if (cnt.find(path - targetSum) != cnt.end()) {
            ret += cnt[path - targetSum];
        }
        
        // 记录当前路径和的出现次数
        cnt[path]++;
        
        // 递归计算左子树和右子树
        _pathSum(node->left, cnt, path, targetSum);
        _pathSum(node->right, cnt, path, targetSum);
        
        // 回溯，恢复现场
        cnt[path]--;
    }

    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, long > cnt;
        cnt[0] = 1; // 初始化前缀和为 0 的情况
        long path = 0;
        _pathSum(root, cnt, path, targetSum);
        return ret;
    }
};